package Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author Kevin
 * @date 2020/3/1 16:31
 */
public class BinarySearchTree {

    //bfs
    private List<Node> floorLevelTree(Node root) {
        if (root == null) return null;
        List<Node> result = new ArrayList<>();
        Node node = root;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);
        while(!queue.isEmpty()) {
            node = queue.poll();
            result.add(node);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if(node.right != null) {
                queue.offer(node.right);
            }
        }
        return result;
    }
    //dfs
    public List<List<Integer>> res = new ArrayList<>();
    public void dfs(Node node, int level) {
        if(node == null) return ;
        if (res.size() <= level) res.add(new ArrayList<>());
        res.get(level).add(node.data);
        dfs(node.left, level+1);
        dfs(node.right, level+1);
    }


    private Node tree;

    public Node find(int data) {
        Node node = tree;
        while(node != null) {
            if (node.data < data) node = node.left;
            else if(node.data > data) node = node.right;
            else return node;
        }
        return null;
    }


    public void insert(int data) {
        if (tree == null) {
            tree = new Node(data);
            return ;
        }
        Node p = tree;
        while(p != null) {
            if (data < p.data) {
                if(p.left == null) {
                    p.left = new Node(data);
                    return ;
                } else {
                    p = p.left;
                }
            } else {
                if (p.right == null) {
                    p.right = new Node(data);
                    return;
                } else {
                    p = p.right;
                }
            }
        }
    }

    public void delete(int data) {
        Node p = tree;
        Node pp = null;
        while(p != null && p.data != data) {
            pp = p;
            if (p.data < data) p = p.right;
            else if(p.data > data) p = p.left;
        }
        if (p == null) return;
        //找到了p，执行删除

        if (p.left != null && p.right != null) {
            Node Minpp = p;
            Node Minp =  p.right;
            while(Minp.left != null) {
                Minpp = Minp;
                Minp = Minp.left;
            }
            p.data = Minp.data;
            pp = Minpp;
            p = Minp;// 下面就变成了删除minP了
        }

        //删除节点时叶子节点或者仅有一个子节点
        Node child;
        if (p.left != null) child = p.left;
        else if (p.right != null) child = p.right;
        else child = null;

        if (pp == null) tree = child;
        else if (pp.left == p) pp.left = child;
        else pp.right = child;
    }

    public static class Node {
        public int data;
        public Node left;
        public Node right;

        public Node(int data) {this.data = data;}
    }
}
